import java.util.*;
/**
 public class TreeNode {
 int val = 0;
 TreeNode left = null;
 TreeNode right = null;

 public TreeNode(int val) {
 this.val = val;

 }

 }
 */
public class Solution {
    TreeNode pre=null;
    TreeNode root=null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null)
            return null;
        // 递归遍历左子树
        Convert(pRootOfTree.left);
        // 判断特殊情况
        if (root==null){
            root=pRootOfTree;
        }
        // 修改遍历的结点为双向链表
        if (pre!= null){
            pRootOfTree.left=pre;
            pre.right=pRootOfTree;
        }
        // 更新 pre
        pre=pRootOfTree;
        // 递归遍历右子树
        Convert(pRootOfTree.right);
        return root;
    }
}